﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
//给你一个 非严格递增排列 的数组 nums ,
//请你原地删除重复出现的元素，使每个元素只出现一次
//返回删除后数组的新长度。元素的 相对顺序 应该保持 一致
//然后返回 nums 中唯一元素的个数。考虑 nums 的唯一元素的数量为 k 
//你需要做以下事情确保你的题解可以被通过：
//更改数组 nums ，使 nums 的前 k 个元素包含唯一元素
//并按照它们最初在 nums 中出现的顺序排列
//nums 的其余元素与 nums 的大小不重要。返回 k 。
; int removeDuplicates(int* nums, int numsSize)
{
    int left = 1;
    int right = 0;
    if (numsSize <= 1)
    {
        return left;
    }
    while (right != numsSize)
    {
        while (nums[left] != nums[right])
        {
            left++;
            right++;
            if (left == numsSize)
            {
                return left;
            }
        }
        while (nums[left] == nums[right])
        {
            right++;
            if (right == numsSize)
            {
                return left;
            }
            while (nums[left] != nums[right])
            {
                nums[left] = nums[right];
                left++;
                nums[left] = nums[right];
                right++;
                if (right == numsSize)
                {
                    return left;
                }
            }
        }
    }
    return left;
}
int removeDuplicates(int* nums, int numsSize) 
{
    if (numsSize == 0) 
    {
        return 0;
    }
    int right = 1, left = 1;
    while (right < numsSize) 
    {
        if (nums[right] != nums[right - 1])
        {
            nums[left] = nums[right];
            ++left;
        }
        ++right;
    }
    return left;
}
//给你一个链表的头节点 head 和一个整数 val 
//请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点
struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode* cur = head;
    struct ListNode* prev = NULL;
    while (cur)
    {
        if (cur->val == val)
        {
            if (cur == head)
            {
                head = cur->next;
                free(cur);
                cur = head;
            }
            else
            {
                prev->next = cur->next;
                free(cur);
                cur = prev->next;
            }
        }
        else
        {
            prev = cur;
            cur = cur->next;
        }
    }
    return head;
}

//给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
//三指针法
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* prev = NULL;
    struct ListNode* cur = head;
    struct ListNode* next = head;
    while (cur)
    {
        if (cur == head)
        {
            next = next->next;
        }
        cur->next = prev;
        prev = cur;
        cur = next;
        if (next != NULL)
            next = next->next;
    }
    return prev;
}

//头插法
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* Newhead = NULL;
    struct ListNode* cur = head;
    while (cur)
    {
        struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));
        temp->val = cur->val;
        temp->next = Newhead;
        Newhead = temp;
        cur = cur->next;
        free(head);
        head = cur;
    }
    return Newhead;
}